package org.example.sort.type;

import java.util.Comparator;

/**
 * 类描述：扫描端点智能更新优化
 * <br>
 *
 * @author ZS
 * @version 1.0
 * @date 2020/12/28
 **/
public class BubbleSort3<E> extends AbstractSort<E> {
    public BubbleSort3() {
        super();
    }

    public BubbleSort3(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    protected E[] sort() {
        // 记录每次扫描最后一次交换的位置，说明该交换之后的元素是局部有序的
        // 可以减少比较次数
        int pos = elements.length;
        for (int end = elements.length - 1; end > 0; end--) {
            // 记录每一轮交换的索引
            pos = 1;
            for (int j = 1; j <= end; j++) {
                if (compare(elements[j - 1], elements[j]) > 0) {
                    swap(j - 1, j);
                    // 记录最后一次交换的位置
                    pos = j;
                }
            }
            end = pos;
        }
        return elements;
    }
}
